#!/usr/bin/python3
import random
from typing import Callable


def binary_search(items: list[int], target: int) -> int:
    """二分查找"""
    return dfs(items, target, 0, len(items) - 1)


def dfs(items: list[int], target: int, low: int, high: int) -> int:
    """二分查找递归。

    Args:
        items (list[int]): _description_
        target (int): _description_
        low (int): _description_
        high (int): _description_

    Returns:
        int: _description_
    """
    if low > high:
        return -1

    middle: int = (low + high) // 2
    if target == items[middle]:
        return middle
    elif target < items[middle]:
        return dfs(items, target, low, middle - 1)
    else:
        return dfs(items, target, middle + 1, high)


def main(size: int = 10, search: Callable = binary_search):
    """
    主函数。
    """
    lyst: int = []
    num: int = 1
    for count in range(size):
        num = num + random.randint(1, 9)
        lyst.append(num)

    data: int = lyst[random.randint(0, size - 1)]

    print(lyst)
    result = search(lyst, data)
    print(data, result)


if __name__ == "__main__":
    main(search=binary_search)
